#if 1
#pragma once
#include<assert.h>

typedef enum{RED = 0, BLACK = 1}ColorType;

template<typename T>
class RBNode
{
public:
	RBNode(
		T _key,
		RBNode<T>* _left = nullptr, 
		RBNode<T>* _parent = nullptr,
		RBNode<T>* _right = nullptr,
		ColorType _color = RED
			)
		:color(_color), 
			key(_key), 
			left(_left), 
			parent(_parent), 
			right(_right) {}

	RBNode<T>* BuyNode(const T& _key, 
					RBNode<T>* _left = nullptr, 
					RBNode<T>* _parent = nullptr, 
					RBNode<T>* _right = nullptr, 
					ColorType _color = RED)
	{
		RBNode<T>* newNode = new RBNode<T>(_key, _left, _parent, _right, _color);
		assert(nullptr != newNode);
		return newNode;
	}
	void FreeNode(RBNode<T>* node)
	{
		delete node; node = nullptr;
	}
public:
	T key;
	ColorType color;
	RBNode<T>* left;
	RBNode<T>* parent;
	RBNode<T>* right;
};

template<typename T>
class RBTree
{
public:
	RBTree();
	~RBTree();

	void InOrder(RBNode<T>* root);
	void NoRecInOrder();
	void MirrorNoRecInOrder();

	bool Insert(const T& key);
	bool Delete(const T& key);

	RBNode<T>* FindValue(RBNode<T>* root, const T& key);
	RBNode<T>* NoRecFindValue(const T& key);

	int GetSize();
	RBNode<T>* GetHead();
	bool IsEmpty();
	bool Is_BSTTree(RBNode<T>* root);
	bool Is_RBTree(RBNode<T>* root);
private:
	RBNode<T>* NextNode(RBNode<T>* node);
	RBNode<T>* PreNode(RBNode<T>* node);
	void RotateLeft(RBNode<T>* node);
	void RotateRight(RBNode<T>* node);
	void LeftBalance(RBNode<T>* node);
	void RightBalance(RBNode<T>* node);
	void AdjustTree(RBNode<T>* node);
private:
	RBNode<T>* head;
	RBNode<T>* NIL;
	int cursize;
};
#endif